package 中等.滑动窗口;

/**
 * 有一个只含有 'Q', 'W', 'E', 'R' 四种字符，且长度为 n 的字符串。
 * 假如在该字符串中，这四个字符都恰好出现 n/4 次，那么它就是一个「平衡字符串」。
 * 给你一个这样的字符串 s，请通过「替换一个子串」的方式，使原字符串 s 变成一个「平衡字符串」。
 * 你可以用和「待替换子串」长度相同的 任何 其他字符串来完成替换。
 * 请返回待替换子串的最小可能长度。
 * 如果原字符串自身就是一个平衡字符串，则返回 0。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/replace-the-substring-for-balanced-string
 */
public class 替换子串得到平衡字符串_1234 {

    public static void main(String[] args) {

        System.out.println(balancedString("EQWRQQQW"));

    }

    /**
     * 滑动窗口
     * 待替换字串外面的 Q W E R 每个字符均不能 > n/4
     * 否则待替换字串怎么换，都不能满足条件
     * 注意：可以用26长度的数组统计字符数量！！！
     */
    public static int balancedString(String s) {
        int ans = s.length();
        char[] chars = s.toCharArray();

        int[] record = new int[26];
        for (char c : chars) {
            record[c - 'A']++;
        }
        int avg = s.length() / 4;

        int left = 0, right = 0;
        while (left < s.length()) {
            while (right < s.length() && (record[4] > avg || record[16] > avg || record[17] > avg || record[22] > avg)) {
                record[chars[right] - 'A']--;
                right++;
            }

            if (record[4] <= avg && record[16] <= avg && record[17] <= avg && record[22] <= avg)
                ans = Math.min(ans, right - left);

            record[chars[left] - 'A']++;
            left++;
        }
        return ans;
    }

}
